package practise.alogrithm.introductionToAlogrithm.dataStructures;

import practise.alogrithm.introductionToAlogrithm.TreeBuilder;
import practise.alogrithm.introductionToAlogrithm.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.Iterator;
import java.util.Stack;

/**
 * Created by Richard on 7/21/2014.
 */
public class BinTreeInIterator <T> implements Iterable<TreeNode<T>> {
    private TreeNode<T> treeNode ;

    public BinTreeInIterator(TreeNode<T> treeNode) {
        this.treeNode = treeNode;
    }

    @Override
    public Iterator<TreeNode<T>> iterator() {
        return new BinTreeIterator<>(treeNode);
    }

    public static void main(String[] args){
        TreeNode<Integer> root = TreeBuilder.createTreeByArrayInWidth(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8});
        BinTreeInIterator<Integer> binTreeSearch = new BinTreeInIterator(root);

        System.out.println("In order");
        for(TreeNode<Integer> treeNode1 : binTreeSearch)
            System.out.print("["+treeNode1.getValue()+"]");
    }
}

class BinTreeIterator <T> implements Iterator<TreeNode<T>>{
    private TreeNode<T> treeNode ;
    private Stack<TreeNode<T>> stackForInorderSearch;
    public BinTreeIterator(TreeNode<T> treeNode){
        this.treeNode = treeNode;
        stackForInorderSearch = new Stack<>();
        //init the stack for inorder at first
        pushAllLeft(treeNode);
    }


    private void pushAllLeft(TreeNode<T> treeNode){
        for(; treeNode!=null;stackForInorderSearch.push(treeNode),treeNode=treeNode.getLeft());
    }

    @Override
    public boolean hasNext() {
        return !stackForInorderSearch.isEmpty();
    }

    @Override
    public TreeNode next() {
        TreeNode<T> node = stackForInorderSearch.pop();
        pushAllLeft(node.getRight());
        return node;
    }
}
